package com.sgg.algorithm.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        int[] temp =new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }


    /**
     * 分合
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }

    }

    /**
     * 治理
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//        System.out.printf("left:%d,right:%d \n",left,right);
        int leftIndex = left;
        int rightIndex = mid + 1;
        int tempIndex=left;
        while (leftIndex <= mid && rightIndex <= right) {
            if (arr[leftIndex] <= arr[rightIndex]) {
                temp[tempIndex] = arr[leftIndex];
                tempIndex++;
                leftIndex++;
            }else {
                temp[tempIndex] = arr[rightIndex];
                tempIndex++;
                rightIndex++;
            }
        }
        while (leftIndex <= mid) {
            temp[tempIndex] = arr[leftIndex];
            tempIndex++;
            leftIndex++;
        }
        while (rightIndex <= right) {
            temp[tempIndex] = arr[rightIndex];
            tempIndex++;
            rightIndex++;
        }
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
}
